package cn.nit.algorithm.experiment;

import java.util.Arrays;
import java.util.Random;

/**
 * 试验一：求解查找假币问题
 *      编写一个程序查找假币问题。有n（n>3)个硬币，其中有一个假币，且假币较轻，
 *      采用天平称重的方式找到这个假币，并给出操作步骤。
 */

public class Experiment3 {
    int[] coins;
    int coinNum;
    public String totalString="";

    public Experiment3() {
        Random random = new Random();
        coinNum = random.nextInt(17) + 4;//假设硬币数量是4~20个；其中一个为假币；
        int fakeCoinIndex = random.nextInt(coinNum);
        System.out.println("本次有硬币一共" + coinNum + "枚");
        totalString+="本次有硬币一共" + coinNum + "枚<br>";
        coins = new int[coinNum];
        //真币的质量设置为3，假币的质量设置为2；
        Arrays.fill(coins, 3);
        coins[fakeCoinIndex] = 2;
        for (int item : coins) {
            System.out.print(item + "  ");
            totalString+=item + "  ";
        }
        System.out.println();
        totalString+="<br>";
    }

    public int balance(int begin, int end) {
        if (end - begin <= 3) {
            if (coins[begin] != coins[begin + 1]) {
                return coins[begin] < coins[begin + 1] ? begin : begin + 1;
            } else {
                return end;
            }
        } else {
            int balanceNum = (end + 1 - begin) / 2;
            int totalFront = 0;
            int totalRear = 0;
            for (int i = begin; i < begin + balanceNum; i++) {
                totalFront += coins[i];
            }
            for (int j = begin + balanceNum; j < begin + balanceNum + balanceNum; j++) {
                totalRear += coins[j];
            }
            if (totalFront < totalRear) {
                return balance(begin, begin + balanceNum - 1);
            } else if (totalFront > totalRear) {
                return balance(begin + balanceNum, begin + balanceNum + balanceNum - 1);
            } else {
                return end;
            }
        }
    }

    public static void main(String[] args) {
        Experiment3 experiment = new Experiment3();
        int fateCoin = experiment.balance(0, experiment.coinNum - 1);
        System.out.println(fateCoin);
    }

    public String runMain(){
        int fateCoin = balance(0, coinNum - 1);
        totalString+="假币的下标为： "+fateCoin+"<br>";
        return totalString;
    }
}
